package com.leetcode.offer.chapter2;

import static java.lang.Math.max;

/**
 * @author Dennis Li
 * @date 2020/7/12 16:39
 */
public class CuttingRope_14 {
    // 注意这里的问题是自底向上的，与常规的自顶向下不同
    // 长度为n最优，等于长度为2时最优，3时最优。。。一直到n最优，累积
    public static int cuttingRope(int n) {
        switch (n) {
            case 0:
            case 1:
                return 0;
            case 2:
                return 1;
            case 3:
                return 2;
            default:
                break;
        }
        int[] num = new int[n + 1];
        for (int i = 0; i < 4; i++) {
            // 赋初始值 -- 注意这道题赋的有点多
            num[i] = i;
        }
        for (int i = 4; i <= n; i++) {
            int temp = 0;
            // 砍一刀下去一定是砍一半，由两部分组成，所以最多能够遍历到i/2
            for (int j = 1; j <= i / 2; j++) {
                temp = Math.max(temp, num[j] * num[i - j]);
            }
            num[i] = temp;
        }
        return num[n];
    }

//    public int cuttingRopeBetter(int n) {
//        int[] dp = {0, 1, 1};
//        // 任何大于3的数都可以拆分为数字1，2,3的和；对3的余数总是0,1,2
//        // 因此我们可以仅用 dp[0]，dp[1]，dp[2] 表示所有大于 3 的值，这样空间复杂度可降到 O(1)。
//        for (int i = 3; i <= n; i++) {
//            int temp = 0;
//            for (int j = 1; j <= 3; j++) {
//                temp = max(temp, j * max(dp[(i - 1) % 3], i - j));
//            }
//            dp[i % 3] = temp;
//        }
//        return dp[n % 3];
//    }

    /* python解法
    * class Solution:
    def cuttingRope(self, n: int) -> int:
        dp = [0 for _ in range(n + 1)]  # dp[0] dp[1]其实没用
        dp[2] = 1  # 初始化
        res = -1
        for i in range(3, n + 1):
            for j in range(i):
                dp[i] = max(dp[i], max((i - j) * j, j * dp[i - j]))
        return dp[n]
    * */

    public static void main(String[] args) {
        int rope = cuttingRope(10);
        System.out.println(rope);
    }
}
